package test230529;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/29 0:28
 * 最小花费爬楼梯
 * https://leetcode.cn/problems/min-cost-climbing-stairs/
 */
public class Solution03 {

    // 动态规划 + 空间优化
    // 时间复杂度O(n), 空间复杂度O(1)
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        // 定义初始量
        int dp0 = cost[0];
        int dp1 = cost[1];
        // 构造状态转移方程: dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i], i >= 2
        for (int i = 2; i <= n; i++) {
            int dpi = Math.min(dp0, dp1) + (i == n ? 0 : cost[i]);
            dp0 = dp1;
            dp1 = dpi;
        }
        return dp1;
    }
}
